import java.util.*;

public class ValidParentheses2 {

    /**
     * 给定一个只包括 '('，')'，'{'，'}'，'['，']'的字符串 s ，
     * 判断字符串是否有效。
     * 有效字符串需满足：
     * 左括号必须用相同类型的右括号闭合。
     * 左括号必须以正确的顺序闭合。
     * @param s
     * @return
     * 解题思路：
     * 初始化栈存储数据
     * 初始化Map存储映射
     * 通过判断栈是否为空来判断true还是false
     */
    public static boolean isValid(String s) {
        int n = s.length();
        if (n%2!=0){
            return false;
        }
        char[] chars = s.toCharArray();
        Map<Character,Character> map = new HashMap<Character,Character>();
        map.put(']','[');
        map.put(')','(');
        map.put('}','{');
        Deque<Character> stacks = new LinkedList<Character>();
        for (int i=0;i<chars.length;i++){
            if (map.containsKey(chars[i])){
                if (stacks.isEmpty()||map.get(chars[i])!=stacks.peek()){
                    return false;
                }
                stacks.pop();
            }else {
                stacks.push(chars[i]);
            }
        }




        return stacks.isEmpty();


    }

    public static void main(String[] args) {
        isValid("()");
    }
}
